Principle of Inclusion and exclusion
We suppose there is a list of property and we assume there is a certain subset of elements that have the property and the rest of the elements do not. We want to get the number of elements that have none of the properties:
- Let
- Count the number of objects having each property which is
, and let be the result - In general look at the
possible subsets of properties. For each of these we count the number of objects haaving all properties in the subset. THen add up all these numbers call it
Theorem: Suppose given k properties and given an n-set X let
be as defined above. Then the number M of elements with none of the properties is given by the formula: